/**
 * 
 */
package org.cuny.sensorslection;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Susan Su
 *
 */
public class DynamicSelector implements ISensorSelector
{

	/* (non-Javadoc)
	 * @see org.ccny.sensorslection.ISensorSelector#calculate(org.ccny.sensorslection.Sensor[], int)
	 */
	public Sensor[] calculate(Sensor[] sensors, int budget)
	{
		int sensorCount = sensors.length;
		int selectionMatrix [][] = new int [ sensorCount+1 ][ budget+1 ];
		
		// fill the dynamic selection matrix
		for ( int tempSensorCount = 1; tempSensorCount <= sensorCount; tempSensorCount++ )
		{
			for ( int tempBudget = 1; tempBudget <= budget; tempBudget++ )
			{
				if ( sensors[ tempSensorCount - 1 ].getCost() <= tempBudget )
				{
					// if (current sensor's value + value of corresponding value with complement budget) > current value
					if ( ( sensors[ tempSensorCount - 1 ].getValue() + 
							selectionMatrix[ tempSensorCount - 1 ][ tempBudget - sensors[ tempSensorCount-1 ].getCost() ] )
							> selectionMatrix[ tempSensorCount - 1 ][ tempBudget ] )
					{
						//tempSensorCount-1 to make sure it starts at 0 
						selectionMatrix[ tempSensorCount ][ tempBudget ] = 
								sensors[ tempSensorCount - 1 ].getValue() + 
								selectionMatrix[ tempSensorCount - 1 ][ tempBudget - sensors[ tempSensorCount - 1 ].getCost() ];
					}
					else
					{
						selectionMatrix[ tempSensorCount ][ tempBudget ]= selectionMatrix[ tempSensorCount - 1 ][ tempBudget ];
					}
				}
				else
				{
					selectionMatrix[ tempSensorCount ][ tempBudget ]= selectionMatrix[ tempSensorCount - 1 ][ tempBudget ];
				}
			}
		}
		
		// pick the elements for optimal set from selection matrix
		List< Sensor > selectedSensors = new ArrayList< Sensor >();
		for ( int sensorNumber = sensorCount; sensorNumber >= 1; sensorNumber-- )
		{
			int tempIter = budget;
			// if there's only one sensor and its cost is less than budget
			if( sensorCount == 1 && sensors[ sensorCount - 1 ].getCost() < budget )
			{
				selectedSensors.add( sensors[ 0 ] );
			}
			//more than one sensor
			else
			{
				while ( selectionMatrix[ sensorNumber ][ tempIter ] == 
						selectionMatrix[ sensorNumber ][ tempIter - 1] && tempIter > 1 )
				{
					tempIter--;	
				}
				
				if ( tempIter > 1 )
				{
					//if selectionMatrix[sensorNumber][tempIter]== selectionMatrix[sensorNumber-1][tempIter], it means current sensor never been selected.
					if( selectionMatrix[ sensorNumber ][ tempIter ] != 
							selectionMatrix[ sensorNumber - 1 ][ tempIter ] )
					{
						selectedSensors.add( sensors[ sensorNumber - 1 ] ); 
						budget = budget - sensors[ sensorNumber - 1 ].getCost();
					}
				}
			}
		}
		
		return selectedSensors.toArray( new Sensor[] {} );
	}

}
